package com.LeeCode;

/**
 * 在 D 天内送达包裹的能力
 */

public class Code1011 {
    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 1, 1};
        int days = 4;
        System.out.println(new Code1011().shipWithinDays(weights, days));
        System.out.println(new Code1011().check(weights, 2, days));
    }

    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = Integer.MAX_VALUE;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(weights, mid, days)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int weight, int days) {
        int sum = 0, count = 1; // 至少需要一天
        for (int num : nums) {
            if (num > weight) { // 确保一件货物能被运走
                return false;
            }
            sum += num;
            if (sum > weight) {
                count++;
                sum = num;
            }
        }
        return count <= days;
    }
}
